
-- array is in a ascending order
local function _binary_search(array, val)
    local s, e = 1, #array
    local mid, v
    while s <= e do
        mid = math.floor((s+e) / 2)
        v = array[mid]

        if val > v then
            s = mid + 1
        elseif val < v then
            e = mid-1
        else
            return mid
        end
    end
    return false
end

local function test()
    local arr = {-1, 0, 1, 2}
    assert(_binary_search(arr, -1) == 1)
    assert(_binary_search(arr, 0) == 2)
    assert(_binary_search(arr, 1) == 3)
    assert(_binary_search(arr, 2) == 4)
end

test()

